package class23;

import class17.KMP1;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class LongestLessSumSubArrayLength2 {

    public static int maxLengthAwesome(int[] arr,int k){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int N = arr.length;
        int[] minSums= new int[N];
        int[] minSumEnds = new int[N];

        minSums[N-1]= arr[N-1];
        minSumEnds[N] = N-1;
        for (int i = N -2;i>=0;i--){
            if (minSums[i+1]<=0){
                minSums[i] = arr[i] + minSums[i+1];
                minSumEnds[i] = minSumEnds[i+1];
            }else {
                minSums[i] = arr[i];
                minSumEnds[i] = i;
            }
        }

        int end = 0;
        int sum = 0;
        int len= 0;
        for (int i = 0;i<N;i++){
            while (end<N && sum + minSums[end] <= k){
                sum += minSums[end];
                end = minSumEnds[end]+1;
            }
            len = Math.max(len,end-i);

            if (end > i){
                sum -= arr[i];
            }else {
                end = i+1;
            }
        }
        return len;
    }
}
